\documentclass [a4paper, 14pt] {vstubachelor}
\usepackage{listings,color}
\definecolor{gray}{rgb}{0.4,0.4,0.4}
\definecolor{darkblue}{rgb}{0.0,0.0,0.6}
\definecolor{cyan}{rgb}{0.0,0.6,0.6}

\author{Чан~В.Ф.}
\title{Разработка модуля визуализации поведения интеллектуальных агентов}
\group{ИВТ-463}
\documentcode{ВРБ--40~461~806--10.27--6--13.81}

\lstset{
  basicstyle=\ttfamily,
  columns=fullflexible,
  showstringspaces=false,
  commentstyle=\color{gray}\upshape
}
 
\lstdefinelanguage{XML}
{
  basicstyle=\ttfamily\color{darkblue}\bfseries,
  morestring=[b]",
  morestring=[s]{>}{<},
  morecomment=[s]{<?}{?>},
  stringstyle=\color{black},
  identifierstyle=\color{darkblue},
  keywordstyle=\color{cyan},
  morekeywords={xmlns,version,type}% list your attributes here
}
\begin {document}
\maketitle
\referenceforresearch
\tableofcontents
\introduction

Мультиагентный подход – это один из современных и активно-развивающихся подходов в области искусственного интеллекта. В настоящее время мультиагентные системы (МАС) применяются в многих областях, в том числе в компьютерных играх. Под интеллектуальным агентом (ИА) в играх понимают агенты, которые самостоятельно принимают решение о выполнении действий на основании результатов анализа состояния окружающей среды – виртуального мира игры. В компьютерных играх оппонентом игрока-человека не другой человек, а персонаж, управляемый компьютером. Программисты компьютерных игр в дальнейшем создают игры, в которых персонажи имеют поведение реального человека.

 С повышением сложности отладка МАС становится нелёгкой. Программисты при разработке МАС трудно  проверять работы агентов в системы. В интеллектуальных играх МАС есть совокупность агентов-персонажей, окружающей среды, алгоритмы взаимодействий между агентами, и т.д.  Поэтому визуализация поведений агентов в МАС становится важным для подготовки специалистов в области МАС. Визуализация поведения ИА полезна в процессе разработки, во время отладки МАС. Должны быть визуализированы координаты агентов, направление движения, направление поиска, текущее действие («думать», поиск, подбор, возврат), а так же пользовательская отладочная информация в виде графических примитивов и текстовых сообщений.
 
В связи с этим целью данной работы являлось повышение эффективности процесса разработки мультиагентных систем, во время их отладки.
 
 Для достижения поставленной цели решались следующие задачи: 
 \begin{enumerate}
\item	Анализ существующих систем для визуализации поведения интеллектуальных агентов;

\item Анализ средств реализации решений;

\item	Исследование алгоритмов визуализации поведений интеллектуальных агентов;

\item	Разработка алгоритмов для визуализации поведения интеллектуальных агентов; 

\item	Проектирование и реализация модуля по созданию и редактированию заданий; 

\item	Тестирование и доработка модуля.
\end{enumerate}

Работа посвящена разработке методов управления агентами, механизмов взаимодействия агентов и разработке модуля визуализации для системы игрового искусственного интеллекта.

Структура и объем данной работы состоит из введения, обзора литературы, 4 глав, заключения и библиографии. Общий объем работы \pageref{LastPage} страниц.
Во введении обоснована актуальность исследования, сформулирована цель работы и перечислены решаемые задачи. 

В первой главе рассмотрена общие сведения о ИА, их характеристики и классификация, проведено исследование существующих систем моделирования МАС, способов визуализации и обзор о средствах для реализации модуля.

Во второй главе описаны разработки алгоритмов визуализации (управления поведения ИА и алгоритма поиска кратчайшего пути), модели агента, модели  визуализации, модели игрового виртуального мира и механизма взаимодействия между ИА.

Во третьей главе проведены выбор инструментов для реализации и проектирование модуля, спроектирована архитектура модуля.

В четвертой главе представлена реализация программы и тестирование модуля.
В заключении работы сформулированы общие выводы и результаты проведенной работы.


\chapter{Анализ алгоритмов, методов анимации и программных средств для их реализации}

\section{Интеллектуальный агент. Определение, характеристики и классификация}

В настоящее время компьютерное моделирование становится широко распространенным и используется для исследования поведения реальных систем.  Различают аналитическое и имитационное моделирование. Аналитическое моделирование рассматривает математические (абстрактные) модели реального объекта в виде алгебраических, дифференциальных и других уравнений. Аналитическое моделирование требует наличия однозначной вычислительной процедуры, приводящей к их точному решению. При имитационном моделировании изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему и с ней проводятся эксперименты с целью получения информации об этой системе. Имитационное моделирование последовательно, шаг за шагом, воспроизводит работу моделируемой системы. Имитационное моделирование часто бывает менее точным, чем аналитическое, например в исследовании непрерывных процессов.

Агентное моделирование является относительно новым направлением и позволяет сглаживать недостатки присущие аналитическому и имитационному моделированию поотдельности. Отличие агентного моделирования от других видов состоит в том, что поведение агентной модели в целом строится из совокупности поведения отдельных индивидуумов --- агентов. Поэтому агентное моделирование используется для исследования децентрализованных систем, динамика функционирования которых определяется не глобальными правилами и законами (как в других парадигмах моделирования), а наоборот, когда эти глобальные правила и законы являются результатом индивидуальной активности членов группы.

Центральным понятием агентного  моделирования является понятие агента. Одно из наиболее популярных определений понятия <<агент>> дали М. Вулдридж и Н. Дженнингс \cite{an-introduction-to-multiagent-systems}

Они считают, что агент --- это программно или аппаратно реализованная система, обладающая следующими свойствами:

\begin {itemize}
	\item автономность --- способность функционировать без прямого вмешательства людей или компьютерных средств и при этом осуществлять самоконтроль над своими действиями и внутренними состояниями;
	\item общественное поведение --- способность взаимодействия с другими, обмениваясь сообщениями с помощью языков коммуникации;
	\item реактивность --- способность воспринимать состояние среды, в которой содержится агент;
	\item целенаправленная активность - способность агентов не просто реагировать на стимулы, поступающие из среды, но и осуществлять целенаправленное поведение, проявляя инициативу.
\end{itemize}

Можно существуют различные классификации агентов, различающиеся  основаниями. В \cite {AgentsMASVirtualSociety, tarasov-from-multiagents-to-intelligence} предложены следующие признаки для классификации агентов:
\begin {enumerate}
	\item явления внешнего мира;
	\item способ  поведения.
\end {enumerate}

В работе Тарасова \cite{AgentsMASVirtualSociety} представлены некоторые классифицикации агентов на основе перечисленных двух различных признаков.
По первому признаку <<явления внешнего мира>> выделяются интеллектуальные (когнитивные, рассудочные) и реактивные агенты. Когнитивные агенты обладают более богатым представлением внешней среды, чем реактивные. Это достигается за счет наличия у них базы знаний и механизма решения. Близкий термин <<рассудочный (deliberative) агент>> служит для обозначения агента, который обладает символьной моделью внешнего мира, а также возможностью принимать решения на основе символьных рассуждений, например, метода сравнения по образцу.

В виртуальном мире компьютерных игр оба вида агентов имеют физические параметры и поведение. Так как  когнитивные агенты содержают много данных, визуализация их поведения становится нелегкой.


Вытекается существенное различие между интеллектуальными и реактивными агентами, связанное с возможностями прогнозирования изменений внешней среды и, как следствие, своего будущего. Реактивные агенты, имеющие довольно бедное внутреннее представление внешней среды (или не имеющие его вовсе), обладают очень ограниченным диапазоном предвидения. Они практически не способны планировать свои действия, поскольку реактивность в чистом виде означает такую структуру обратной связи, которая не содержит механизмов прогноза.  В то же время когнитивные агенты, благодаря развитым внутренним представлениям внешней среды и возможностям рассуждений, могут запоминать и анализировать различные ситуации, предвидеть возможные реакции на свои действия,    делать   из  этого   выводы,   полезные  для  дальнейших  действий   и,  в   результате, планировать свое поведение. Именно интеллектуальные способности позволяют таким агентам строить виртуальные миры, работая в которых они формируют планы действий.

Когнитивные агенты имеют ярче выраженную индивидуальность, будучи гораздо более автономными, чем реактивные, и характеризуются развитым целесообразным поведением в сообществе агентов, достаточно не зависимым от других агентов.   С другой стороны,   реактивные агенты как это видно из самого их названия, работают в основном на уровне стимульно-реактивных связей, обладая очень бедной индивидуальностью и сильной зависимостью от внешней среды (сообщества агентов). 



Результаты сравнительного анализа реактивных и когнитивных агентов представлены в таблице \ref {table:AgentClassification}.


\begin {table}[h]	
	\caption {Классификация агентов}
	\label {table:AgentClassification}
	\begin {tabularx} {\linewidth} {|c|X|X|}
		\hline
			Характеристики							& Когнитивный агент				&	Реактивный агент		\\
		\hline
			Внутренняя модель внешнего мира	& Развитая							& 	Примитивная				\\
		\hline
			Рассуждения								& Сложные и рефлексифные		& Простые одношаговые	\\
		\hline
			Мотивация								& Развитая система мотивации, включающая  убеждения,  желания, намерения				& Простейшие побуждения, связанные с выживанием \\
		\hline
			Память									&	Есть								& Нет							\\
		\hline
			Реакция									&	Медленная						& Быстрая					\\
		\hline
			Адаптивность								&	Малая								& Высокая	\\
		\hline
			Модульная архитектура					&	Есть								&	Нет		\\
		\hline
			Состав МАС								&	Небольшое число автономных агентов &	Большое число зависимых друг от друга агентов \\
		\hline

	\end{tabularx}
\end {table}

Но наиболее важным основанием для классификации можно назвать степень интеллектуальности агентов, то есть их модель поведения по отношению к окружающему миру. В одном случае, речь идет о трактовке агентов как объектов, самостоятельно решающих встающие перед ними задачи, а в другом они уподобляются простейшим организмам, непосредственно реагирующим на изменения среды в интересах выживания и адаптации.

Сложность дает трудности при исследовании и разработке МАС. Моделирование становится важным в области разработки МАС. В туториале \cite{TutorialsAgent-based} представлены моделирование и	 визуализация поведения базовых агентов.

С точки зрения программирования вытекались системы, разработанные на основе мультиагентного подхода. Опытные программисты публикали довольно много книг о разработке системы ИИ. В том числе книга <<Progamming-Game-AI-by-Example>>, автор Mat Buckland  \cite{Progamming-Game-AI-by-Example}. В этой книге автор вглядил системы ИИ от зрения разработчиков компьютерных игр. Кроме того что разработаны примеры систем ИИ, автор визуализировал поведние агентов в таких системах.

\section{Анализ систем моделирования интеллектуальных агентов}
Существуются немало систем моделирования поведения агетов. В том числе можно перечислять следующие системы: 
\begin{itemize}
\item система моделирования «NetLogo»
\item система моделирования «MASON»
\item система моделирования «Ascape»
\item система моделирования «Repast»
\end{itemize}

Такие системы реализованы на основе мультиагентного подхода. Рассмотрим их последовательно, анализируя функции этих систем и методы визуализации, которые в них используются.
 
\subsection{NetLogo}

Система NetLogo \cite{NetLogoSystem} %[Система моделирования "NetLogo" / http://ccl.northwestern.edu/netlogo]. 
%http://netlogo.livejournal.com/
является следующим поколением серии языков мультиагентного моделирования, которая стартовала с проекта StarLogo. Ури Виленский разработал её  в 1999 году, с тех пор она постоянно развивается Центром подключенного обучения и компьютерно-ориентированного моделирования. %проверить перевод (Centre connected learning)
Система позволяет студентам создавать модели и эксперементировать с ними, изучая их поведение при различных условиях. Кроме того, существует среда разработки, которая позволяет студентам, преподавателям разрабатывать учебные программы для создания собственных моделей. NetLogo достаточно прост, так что студенты и учителя могут легко запускать симуляции или даже создавать свои собственные, достаточно продвинутые и качественные. 

NetLogo --- мощный инструмент для исследователей во многих областях, имеет развитую документацию и обучающие материалы. Он также поставляется с библиотекой моделей, которая содержит большую коллекцию предварительно написанных моделей, которые можно использовать и модифицировать. Эти симуляции относятся к многим областям в естественных и социальных науках, в том числе биологии и медицины, физики и химии, математики и информатики,  экономики и социальной психологии. Существует инструмент для совместного участия в моделировании, он называется HubNet. Благодаря использованию сетевых компьютеров или портативных устройств, таких как графический калькулятор Texas Instruments, каждый участник может контролировать агента в симуляции. 

Для создания моделей агентов и настройки свойств системы используются такие элементы, как <<Мониторы>>, <<переключатели>> и <<метки>> для смотра состояния системы: количество агентов, их <<энергия>>, их состояние и т.д. В интерфейсной части строятся графики и осуществляется работа с цветом. Функции могут быть экспортированы или импортированы(экспорт данных, сохранение и восстановление состояния модели, создание роликов).

\subsection{MASON}
%[Система моделирования "MASON"/ http://cs.gmu.edu/~eclab/projects/mason] 
Агентно-ориентированная система моделирования MASON\cite {Mason} --- это быстрая дискретно-ориентированная мультиагентная среда моделирования, представленная в виде набора библиотек на Java. Характерна такая особенность, как отделение модели от представления, что делает возможным переключение между различными визуализациями. Также модели являются воспроизводимыми, что делает возможным повторение моделирования даже на различных платформах.
Раработчики системы --- это: Sean Luke, Gabriel Catalin Balan, Keith Sullivan, and Liviu Panait, с помощью следующих программистов Claudio Cioffi-Revilla, Sean Paus, Keith Sullivan, Daniel Kuebrich, Joey Harrison, and Ankur Desai. % Транслитерировать имена или возможно написать компанию-разработчика вместо длинного списка имен

Система моделирования Mason позволяет визуализировать и манипулировать моделями в 2D и 3D (с помощью Java3D), и которые могут производить скриншоты и видео.
%[MASON: A New Multi-Agent Simulation Toolkit. Sean Luke, Claudio Ciofﬁ-Revilla, Liviu Panait, and Keith Sullivan]
Система рассчитана на студентов и преподавателей, которые исследуют направление моделирования мультиагентных систем.

В \cite{MasonToolkit} описана система моделирования <<MASON>> и представлена архитектура визуализации поведение ИА на основе мультиагентного подхода.Все элементы модели Мейсона и визуализации автономных слоев и могут быть легко заменены или расширены.

На рисунке \ref{fig:masonFigure} представлены основные элементы модели Мейсон и визуализации слоев.

\begin{figure}[!ht]
\includegraphics[scale=1]
{masonFigure.png}
\caption{\label{fig:masonFigure}Основные элементы модели Мейсон и визуализации слоев}
\end{figure}

\subsection{Ascape}
%[Система моделирования "Ascape" / http://ascape.sourceforge.net/index.html%23Contact]. http://ascape.sourceforge.net
Система Ascape\cite {Ascape} --- система моделирования, основанная на агентах и предназначенная для моделирования в общих целях. Она разработана для того, чтобы быть достаточно гибкой и мощной, но в тоже самое время и легкой для использования и представления результатов. Модели могут быть реализованы в Ascape с использованием меньшего количества кода, чем в других средах такого же рода. Это достигается с помощью высокоуровневого фреймворка поддерживающего комплексное проектирование модели, что позволяет пользователям без квалификации программиста постигать многие аспекты динамического моделирования. Система разработана компанией Miles Parker Development. % Проверить название компании

\subsection{Repast}
%[Система моделирования "Repast"/ http://repast.sourceforge.net/].
Назначение: Система Repast\cite {Repast} разработана Mark Altaweel, Dariusz Blachowicz, Mark Bragen, Carl Burke, и представляет собой кросс-платформенную систему моделирования с широкими возможностями интероперабельности и интегрируемости. Она поддерживает разработку наиболее гибких систем взаимодействия агентов для проведения процедуры моделирования на рабочих станциях и небольших вычислительных кластерах. Система Repast позволяет задавать модель различными языками: Groovy\cite{Groovy} --- динамический языком для виртуальной машины Java , Java, ReLogo. Среда моделирования полностью объектно-ориентированная и поддерживает набор встроенных средств для обработки результатов моделирования (MatLab, SQL, Excel и так далее). %"Groovy"/ http://groovy.codehaus.org/]

Система позволяет динамически получить доступ к свойствам агента, уравнениям поведения агента, свойствам модели и изменить их. Система поддерживает работу  с библиотеками генетических алгоритмов, нейронных сетей, генерации случайных чисел, и специализированной математики, также интегрирована поддержка географических информационных систем (ГИС).

\subsection{Выводы}

Ниже приводится сравнительная таблица \ref {table:MASSystems} существующих систем визуализации мультиагентов по различным критериям. В таблице показываны четыре системы для визуализации мультиагентов. Они позволяют лече создать мультиагентные системы. Опытный программист может создавать функции для модели агента, настроить или контролировать параметры агентов. 

\begin {table} [h]
	\caption{Сравнительная таблица существующих систем }
	\label{table:MASSystems}
	\begin {tabularx}{\linewidth}{|c|X|X|X|X|}
		\hline
			Критерий							&	NetLogo	&	Mason	&	Ascape		&	Repast		\\
		\hline
			Независимая работа агентов	&	Да			&	Да		&	Да			&	Да			\\
		\hline
			Способ визуализации			&	2D 			& 2D, 3D 	&	2D 			&	2D 			\\
		\hline
			Доступ к коду					&	Да			&	Да		&	Да			&	Да			\\
		\hline
		
	\end{tabularx}
\end {table}
Во всех системах существуют модули визуализации поведения ИА. Но отладочная информация отображается в формате тектовом и графическом формате независимо от положения агента в окружающей среде. Это снижает эффективность процесса отладки, так как разработчик должен фокусировать внимание на двух объектах: агенте и таблице с информацией о нем.

Эти системы моделирования визуализируют состояния виртуального мира и  поведение агентов. В системе «NetLogo» визуализируются параметры о количестве  и энергии агентов с помощью графики. Другие параметры агентов не показываются, например, скорость, направление движения, поведение и т.д.

\section{Анализ способов визуализации поведения интеллектуальных агентов}

Визуализация ИА подразумевает анимацию 3D с 2D физикой и поведение интеллектуальных агентов. Поведение агента изменяется в соответствии с конкретной систуацией и визуально отображается с помощью отладной информации.

Требования к качеству визуализации могут быть следующими образами:
\begin {itemize}
	\item высокая скорость выполнения визуализации ИА;
	\item возможности визализировать отладную информацию;
	\item возможность модифицировать объекты в процессе выполнения;
	\item объединение действия моделей как в реальной систуации.
\end {itemize}

Для визуализации 3D-объектов нужна анимация. Существует два основных типа: анимации вершинная и скелетная анимация. Эти типы анимации используются в различных ситуациях и каждый имеет свои преимущества и недостатки.

В \cite{animationford} посвящена классификация 3D-анимации и как создать модель с 3D-анимацией. Автор представил опыт работы с скелетной и вершинной анимациям на DirectX, и форматы файлов, в которых содержатся модели с конкретной анимацией. %[http://netlib.narod.ru/library/book0077/ch11_01.htm]

\subsection{Вершинная анимация}
Вершинная --- один из способов 3D-анимации, использующий во многих компьютерных играх.
Вершинная (или вертексная) анимация характерна тем, что для формирования анимационной последовательности программа перемещает каждую вершину модели от одной позиции к другой. Этот тип анимации впервые был применен в Quake, и с тех пор форматы моделей серии Quake (MD2, MD3) стали своего рода стандартом во всех популяных движках. Xtreme3D предоставляет полную поддержку MD2 и частичную --- MD3. Разница между ними заключается в том, что MD2 хранит всю модель целиком в одном файле, а MD3 --- в трех (отдельно голова, туловище и ноги). При помощи специальных матриц туловище синхронизируется с ногами, а голова --- с туловищем. Это было сделано для того, чтобы анимировать туловище и ноги по отдельности. Например, во время стрельбы персонаж мог как бежать, так и идти медленно, а то и просто стоять на месте. 

Вершинная анимация основана на том, что положение вершин в пространстве может изменяться, но не может меняться их связь с другими вершинами. Для создании анимации неодходимо создать последовательность из ключевых кадров. Каждый ключевой кадр --- это фактически информация о положении каждой вершины в пространстве. Вершины определяют вид объекта для каждого кадра анимации, и каждый из этих кадров может входить в отдельную анимационную последовательнось. Анимация осуществляется последовательным проходжением по кадрам анимации. Однако такой может сопровождаться «рывками». Для получения более плавной анимации необходимо использовать линейную интерполяцию между кадрами. Например, мы хотим провести интерполяцию с коэффициентом 0.25 от кадра i до кадра i+1. При этом будет осуществлён плавный переход координат вершин от кадра i до кадра i+1 c интерполяционными значениями 0, 0.25, 0.50, 0.75.

Фактически, существует два подтипа вершинной анимации: морфинг и анмация позы. Морфинг --- это очень простой способ, который интерполирует снимки сетки по ключевым кадрам временной шкалы. Морфинг имеет прямое отношение к методам старой школы анимации персонажей, используемыми до того, как повсеместно стала использоваться скелетная анимация. Анимация позы - это смешивание нескольких дискретных поз, выраженная как отклонение от базовых вершинных данных с различными весами для обеспечения окончательного результата. Наиболее очевидным использованием анимация позы является лицевая анимация.

\subsection{Скелетная анимация} 
Один из способов анимации 3D-моделей является скелетной анимацией. Он широко применяется в 3D компьютерных играх. Особенно впервые в играх скелетная анимация появилась в игре Half-Life (1998) \cite{Half-Life-Game}.
 Для cкелетной анимации необходимо построить скелет модели, состоящий из нескольких костей, и затем присоединить каждую вершину сетки к кости скелета. В результате при анимации скелета анимируется также и присоединенная к нему сетка, следуя анимации скелета.

Чтобы построить сетку модели, скелет и анимацию, можно использовать различные программы моделирования, поддерживающие скелетную (или костевую) анимацию, такие как 3ds Max, Maya, Blender и т.д.  После того, как создать модель, надо экспортировать ее в формат, поддерживающий скелетную анимацию. Заметим, что скелетная анимация является также анимацией с ключевыми кадрами, а это значит, что экспортируются только ключевые кадры скелетной анимации. Как и в анимации с ключевыми кадрами можно интерполировать кадры анимации скелета. В основе скелетной анимации лежит скелетная структура объекта, то есть набор иерархически упорядоченных костей, к которым уже крепиться часть визуального представления объекта (наботы вершин). Одна кость, которая казывается корневой, формирует точку опоры для всей скелетной структуры. Все остальные крепятся к корневой, как потомки. Каждая кость содержит свою трехмерную преобразование (позиция, размер, ориентация), и, возможно, кость-родитель. Преобразоваия задаются матрицами размерности 4x3 или 4x4. Полное преобразование кости-потомка --- произведение проеобразования родителя с её собственным преобразованием. Соответственно при изменении положения кости-родителя все её кости-потомки также изменят своё положение. Получается, что анимация достигается за счёт изменения преобразований костей во времени. Сама анимация может либо браться из готовых просчитанных заранее положений каждой кости, либо вычисляться процедурно - некоторым контроллером анимации. Если какая-то кость поменяла своё расположение в пространстве, то есть изменилась её абсолютная матрица трансформации, то требуется заново сделать пересчёт всех дочерних костей. Во время анимации просчёт скелета нужно делать в каждый момент времени.

Скелетная анимация обладает несколькими преимуществами по сравнению с анимацией с ключевыми кадрами. Она позволяет легко смешивать анимации, позволяя одновременно применять к модели различные анимации. Скелетная анимация также позволяет соединять кости одного объекта с костями другого. Например, если персонаж, который орудует мечом, то можно присоединить кость меча к кости руки персонажа, в результате чего меч будет перемещаться при перемещении руки персонажа. Сегодня скелетная анимация используется более широко, чем анимация с ключевыми кадрами. Держа это в уме мы сосредоточимся на скелетной анимации.

Скелетная анимация также как технология используется в двумерной компьютерной мультипликации, например, в векторном редакторе мультипликации Anime Studio (бывшая Moho) или открытом Synfig Studio. Принцип действия такой же: отдельные фрагменты модели <<привязываются>> к костям, и далее мультипликатор, вместо того чтобы отрисовывать модель в каждом кадре, задаёт движения костям. Модель персонажа двигается, повторяя движения скелета.

\subsection{Выводы}
Результаты анализа способов анимации приведены в таблице \ref{table:Animations}.

\begin {table}[h]
	\caption {Анализ способов анимации}
	\label {table:Animations}
	\begin {tabularx}{\linewidth}{|c|X|X|}
		\hline
			Критерий						&	Вершинная анимация		&	Скелетная анимация	\\
		\hline
			Производительность			& 	Средняя						&	Высокая					\\
		\hline
			Популярность в 3D-играх	&	Низкая						&	Высокая					\\
		\hline
			Подержка формата .b3d &	-&+ \\
		\hline
			Возможность создание визуального эффекта & + & + \\
		\hline
		
	\end {tabularx}
\end{table}

На основе результатов анализа достоинства и недостатки существующих способов  визуализации, были сделаны выводы:
\begin {itemize}
	\item имеется возможность использования их для работы над модулями визуализации поведения ИА.
	\item Скелетная анимация популярна, чем вершинная анимация. Эта анимация широко используется в 3D играх с высокой скоростью выполнения.
   	\item Скелетная анимация лучше для визуализации, поэтому в рамках работы будет выбран .b3d.
\end {itemize}

Разрабатываемый в рамках бакалаврской работы, модуль должен содержать модели с скелетной анимацией.

\section{Обзор существующих средств разработки модлуля}

Для разработки модуля может быть использовано низкоуровневое или высокоуровневое API. К низкоуровневым интерфейсам можно отнести DirectX \cite{DirectXGraphics}, OpenGL \cite{openGLGraphics} и GDI+. Из высокоуровневых будут рассматриваться Ogre и Irrlicht SDK.

OpenGL и Direct3D --- две основные на сегодняшний день аппаратно-ускоряемые библиотеки для создания компьютерной трехмерной графики, а также библиотека GDI+ (дополненная GDI), предназначенная для работы в рамках Microsoft .NET Framework, также основанная на OpenGL и Direct3D, и представляет собою набор классов. Эти классы инкапсулируют поведение объектов и инструментов, предназначенных для рисования. 

OGRE (Object Oriented Graphics Engine) --- это кросс-платформенное SDK для создания графических приложений \cite{OrgeEngine}. Фреймворк имеет довольно обширные возможности, такие как полная поддержка OpenGL и Direct3D, полная совместимость с платформами Windows, Linux, Mac OS X и iOS, поддержка большого количества различных файловых форматов, продвинутая система частиц, использование GPU и всех шейдерных языков высокого уровня и многое другое.


IrrLicht (IrrLicht3d) --- свободный мультиплатформеный графический 3D-движок.

% Havok я выкинул, так как это физика, а не графика


\subsection{Библиотека Direct3D}

В настоящий день графический API DirectX намного больше и чаще используется в игровых движках, чем OPENGL, потому что DIRECTX развивается гораздо быстрее, как и технические средства и возможности. 
Можно сказать, что они определяют будущие возможности технических средств и предоставляют усовершенствованные инструменты разработчикам компьютерных игр.

Фундаментальная задача аппаратно-ускоряемого графического API --- дать возможность прикладным программистам использовать последние достижения быстро развивающейся технологии ускорителей трехмерной графики и в то же время добиться совместимости и унификации решений на разных аппаратных платформах.

В DirectX 9.0 функциональность DirectDraw и Direct3D была объединена в единый API, названный DirectX Graphics. Direct3D, часть этого компонента, представляет наибольший интерес. Microsoft Direct3D предоставляет программисту выбор из двух вариантов: использовать конвейер стандартных функций или программируемый конвейер. Первый полагается на алгоритмы, реализованные и стандартизированные в Direct3D. Стандартные функции предоставляются через фиксированный набор перечислимых значений по аналогии с OpenGL. Это подразумевает, что конвейеры стандартных функций и в Direct3D, и в OpenGL используют внутренние операторы switch. Некоторые из блоков case, соответствующих перечислимому значению в операторе switch, могут выполняться с аппаратным ускорением в зависимости от функциональности графической платы, с которой имеет дело исполняющая среда. При использовании конвейера стандартных функций в Direct3D программист сначала проверяет через исполняющую среду, поддерживает ли данная графическая плата конкретную функциональность.

Поскольку некоторые графические платы поддерживают не все функции, доступные через Direct3D, предусмотрен механизм проверки возможностей аппаратного обеспечения. Если данная функция не поддерживается аппаратно, проверка заканчивается неудачей, что позволяет программисту переключиться на другой алгоритм с аппаратным ускорением. В Direct3D есть режим чисто программной эмуляции, также называемый эталонным устройством (null reference device), он предназначен только для отладки и тестирования.

Другой, более интересный подход к проблеме параллельной эволюции аппаратного и программного обеспечения --- применение программируемого конвейера. В этом случае вместо выбора предопределенного перечислимого значения и запроса к Direct3D на выполнение соответствующего алгоритма программист определяет собственный алгоритм. Исполняющая среда Direct3D динамически компилирует этот алгоритм для нижележащего аппаратного обеспечения, взаимодействуя с JIT-компилятором, который является частью драйвера устройства. За создание JIT-компиляторов для конкретных графических устройств отвечают поставщики оборудования. Таким образом, Direct3D выступает в роли графической виртуальной машины, которая фактически виртуализирует графический процессор на основе пользовательского набора команд для графических операций.

Хотя оба программных уровня Direct3D (управляемый и неуправляемый) предоставляются через группы объектов, не следует считать их инфраструктурой программирования прикладного уровня. Основная роль архитектуры Direct3D --- обеспечить доступ к базовой функциональности решениям более высокого уровня, например API игровых движков. Чтобы упростить реализацию таких решений, библиотека расширений Direct3D явным образом предоставляет дополнительную функциональность. Конвейер Direct3D следует рассматривать как набор алгоритмов, выполняющих операции над трехмерными геометрическими величинами, каковыми в случае Direct3D являются предопределенные вершины и примитивы. Основное предназначение конвейера — преобразование геометрических данных в изображение, формируемое на экране. Этап тесселяции в Direct3D — разбиение на треугольники фиксированного набора предопределенных примитивов более высокого порядка, в том числе треугольных, прямоугольных  и полигональных участков поверхностей. 
Для большего быстродействия на этапе растеризации любые вершины невидимых камере объектов вырезаются. А чтобы избежать растеризации треугольников, отвернутых от камеры, может выполняться операция отсечения невидимых поверхностей. Более того, для выбора и настройки реальных алгоритмов, которые будут задействованы на этапе растеризации, используется оценка атрибутов. Наконец, после всех этих оптимизаций начинается собственно растеризация, в ходе которой осуществляется рендеринг пикселов.

На этапе обработки пикселов  для определения значения цвета пиксела могут быть использованы либо мультитекстурирование на основе стандартных функций , либо программируемые пиксельные шейдеры. Мультитекстурирование на основе стандартных функций реализуется за счет многопроходного наложения текстур, причем на каждом проходе над значениями цвета и прозрачности пиксела можно выполнять фиксированный набор операций. Пиксельные шейдеры дают гораздо большую гибкость, позволяя оперировать значениями цвета и прозрачности на собственном языке ассемблера. Алгоритмы, реализованные на этапе обработки пикселов, включают наложение рельефа, затенение, наложение карты среды и т. д.

При обработке буфера кадра используется набор регионов памяти, известных как поверхность рендеринга, буфер глубины и буфер шаблонов. На этом этапе выполняется серия вычислений для определения таких параметров, как глубина, прозрачность и шаблон. Буфер глубины --- это еще один метод оптимизации рендеринга, применяемый для удаления скрытых линий и поверхностей. Проверка глубины позволяет выяснить, какие пикселы скрыты и не нуждаются в рендеринге. При этом используется либо z-буфер, либо w-буфер (у каждого из них свои плюсы и минусы). Обработка буфера кадра дает возможность создавать ряд эффектов, в том числе прозрачность, туман и тени.

Таким образом, библиотека Direct3D имеет возможности для создания хороших компьютерных играх. Програмисты игр должны имеет знание 3D графику и следует, Direct3D дает неограниченную возможности для разработки игр.

\subsection{Библиотека OpenGL}

В данной разделе рассматривается стандартная графическая библиотека - OpenGL.

В сегодняшний день производители программного обеспечения столкнулись с серьёзной проблемой - это отсутствие каких-либо стандартов, которые позволяли писать программы, независимые от оборудования и операционной системы. Одним из первых таких стандартов, существующий и по сей день является OpenGL.

OpenGL - это графический стандарт в области компьютерной графики \cite{OpenGlStaldart}. На данный момент он является одним из самых популярных графических стандартов во всём мире. В 1982 г. в Стенфордском университете была разработана концепция графической машины, на основе которой фирма Silicon Graphics в своей рабочей станции Silicon IRIS реализовала конвейер рендеринга. Таким образом была разработана графическая библиотека IRIS GL. На основе библиотеки IRIS GL, в 1992 году был разработан и утверждён графический стандарт OpenGL. Разработчики OpenGL - это крупнейшие фирмы разработчики как оборудования так и программного обеспечения: Silicon Graphics, Inc., Microsoft, IBM Corporation, Sun Microsystems, Inc., Digital Equipment Corporation (DEC), Evans \& Sutherland, Hewlett-Packard Corporation, Intel Corporation и Intergraph Corporation.

OpenGL переводится как Открытая Графическая Библиотека (Open Graphics Library), это означает, что OpenGL - это открытый и мобильный стандарт. Программы, написанные с помощью OpenGL можно переносить практически на любые платформы (Linux, MacOS, Windows, и т.д.), получая при этом одинаковый результат, будь это графическая станция или суперкомпьютер. OpenGL освобождает программиста от написания программ для конкретного оборудования. Если устройство поддерживает какую-то функцию, то эта функция выполняется аппаратно, если нет, то библиотека выполняет её программно.

С точки зрения программиста OpenGL - это программный интерфейс для графических устройств, таких как графические ускорители. Он включает в себя около 150 различных команд, с помощью которых программист может определять различные объекты и производить рендеринг. Говоря более простым языком, вы определяете объекты, задаёте их местоположение в трёхмерном пространстве, определяете другие параметры (поворот, масштаб, ...), задаёте свойства объектов (цвет, текстура, материал, ...), положение наблюдателя, а библиотека OpenGL позаботится о том чтобы отобразить всё это на экране. Поэтому можно сказать, что библиотека OpenGL является только воспроизводящей (Rendering), и занимается только отображением 3Д обьектов, она не работает с устройствами ввода (клавиатуры, мыши). Также она не поддерживает менеджер окон.

OpenGL имеет хорошо продуманную внутреннюю структуру и довольно простой процедурный интерфейс. Несмотря на это с помощью OpenGL можно создавать сложные и мощные программные комплексы, затрачивая при этом минимальное время по сравнению с другими графическими библиотеками.

В некоторых библиотеках OpenGL (например под X Windows) имеется возможность изображать результат не только на локальной машине, но также и по сети. Приложение, которое вырабатывает команды OpenGL называется клиентом, а приложение, которое получает эти команды и отображает результат --- сервером.

 Таким образом можно строить очень мощные воспроизводящие комплексы на основе нескольких рабочих станций или серверов, соединённых сетью. 
  
 OpenGL даёт программистам найболее возможности разработки графических приложений, особенно с 3D графикой. 
 
 Можно перечислять следующие основные возможности библиотеки OpenGL:

\begin {itemize}
	\item геометрические и растровые примитивы. На основе геометрических и растровых примитивов строятся все объекты. Из геометрических примитивов библиотека предоставляет: точки, линии, полигоны. Из растровых: битовый массив(bitmap) и образ(image)
	\item использование В-сплайнов. B-сплайны используются для рисования кривых по опорным точкам.
	\item видовые и модельные преобразования. С помощью этих преобразований можно располагать обьекты в пространстве, вращать их, изменять форму, а также изменять положение камеры, из которой ведётся наблюдение.
	\item работа с цветом. OpenGL предоставляет программисту возможность работы с цветом в режиме RGBA (красный-зелёный-синий-альфа) или, используя индексный режим, где цвет выбирается из палитры.
	\item удаление невидимых линий и поверхностей. Z-буферизация.
	\item Двойная буферизация. OpenGL предоставляет как одинарную, так и двойную буферизацию. Двойная буферизация используется для того, чтобы устранить мерцание при мультипликации, т.е. изображение каждого кадра сначала рисуется во втором (невидимом) буфере, а потом, когда кадр полностью нарисован, весь буфер отображается на экране.
	\item наложение текстуры. Позволяет придавать объектам реалистичность. На объект, например шар, накладывается текстура(просто какое-то изображение), в результате чего наш объект теперь выглядит не просто как шар, а как разноцветный мячик.
	\item сглаживание. Сглаживание позволяет скрыть ступенчатость, свойственную растровым дисплеям. Сглаживание изменяет интенсивность и цвет пикселей около линии, при этом линия смотрится на экране без всяких зигзагов.
	\item освещение. Позволяет задавать источники света, их расположение, интенсивность, и т.д.
	\item атмосферные эффекты. Например туман, дым. Всё это также позволяет придать объектам или сцене реалистичность, а также "почувствовать" глубину сцены.
	\item прозрачность объектов.
\end {itemize}

Библиотека OpenGL содержит немного функций для работы с 3D графикой, но она даёт разботчикам игр многие возможности для создания графических игр с "нуля".

\subsection{Библиотека GDI+}%[ http://www.rsdn.ru/article/gdi/gdiplus2mag.xml]

Одна библиотека, содержающая специфические вожможности для создания графических приложений на основе 2D графики, является GDI+. Настоящие программисты считают, что GDI+ --- графика нового поколения. 
Далее в работе рассматриваются возможности и концепция такой библиотеки.

GDI+ - это набор программных средств, которые используются в .NET \cite{GDIPlus}. GDI+ позволяют создателям приложений выводить данные на экран или на принтер без необходимости обеспечивать работу с определенными типами устройств отображения. Для отображения информации программисту достаточно вызывать нужные методы классов GDI+. При этом автоматически учитываются типы определенных устройств и выполняются вызовы соответствующих драйверов. Интерфейс GDI+ является развитием GDI (Graphic User Interace), использованного в ранних версиях Windows. Таким образом, модификация GDI для .NET называется GDI+.

При создании ОС Microsoft Windows компания Microsoft избавила программистов от необходимости учитывать аппаратные особенности видеоадаптеров, переложив эту задачу на драйверы видеоадаптеров. Эти драйверы создаются разработчиками видеоадаптеров и наилучшим образом реализуют возможности аппаратуры.
Что же касается приложений, то для них в составе ОС Microsoft Windows был предусмотрен набор системных функций, реализующих интерфейс графических устройств (Graphics Device Interface, GDI). Интерфейс графических устройств GDI, как это можно предположить из названия, предназначен для взаимодействия приложений Microsoft Windows с графическими устройствами, такими как видеоадаптер, принтер или плоттер.

Когда приложения обращаются к GDI для выполнения операции вывода графического изображения, они работают не с реальными (физическими) устройствами вывода, а с логическими устройствами. Приложения Microsoft Windows не определяют тип видеоадаптера (EGA, VGA, SVGA и т.п.), а работают с логическим видеоадаптером, имеющим феноменальные характеристики: способность отображать практически любой цвет, имеющим огромное разрешение и т. д. Выполняя запрос приложения, GDI обращается к драйверу соответствующего устройства вывода, работающему, в свою очередь, непосредственно с физическим устройством вывода. В процессе выполнения запроса GDI (или драйвер) учитывает ограниченные возможности видеоадаптера и его аппаратные особенности, делая необходимые приближения. Например, приложение может указать для цвета линии любой из примерно 16 млн. цветов, однако не всякое устройство обладает таким цветовым разрешением (ограничения на количество одновременно отображаемых цветов присутствуют, например, в карманных компьютерах). В зависимости от типа физического устройства, используемого для вывода, GDI может выбрать для отображения цвет, наиболее соответствующий запрошенному цвету, и допустимый для устройства. Например, если устройство вывода монохромное, вместо различных цветов могут использоваться градации серого цвета. Поэтому приложение может запросить для вывода любой цвет, но для рисования будет использован только такой, который может использовать данное физическое устройство.

Контекст отображения можно сравнить с листом бумаги, на котором приложение рисует то или иное графическое изображение, а также пишет текст. Инструменты для рисования — это перья, кисти (а также шрифты и даже целые графические изображения), с помощью которых создается изображение.
Кроме контекста отображения и инструментов для рисования, приложениям доступны десятки функций программного интерфейса GDI, предназначенные для работы с контекстом отображения и инструментами. Что же касается приложений Microsoft .NET Framework, то они реализуют возможности интерфейса GDI+ с помощью набора соответствующих классов и интерфейсов.

В терминах ОС Microsoft Windows контекст отображения (display context) представляет собой структуру данных, описывающую устройство отображения. В этой структуре хранятся различные характеристики устройства и набор инструментов для рисования, выбранный по умолчанию. Приложение может выбирать в контекст отображения различные инструменты (например, перья различной толщины и цвета, с различными «наконечниками»). Поэтому если  надо нарисовать линию красного или зеленого цвета, перед выполнением операции следует выбрать в контекст отображения соответствующее перо.
Заметим, что функции рисования GDI, входящие в программный интерфейс Win32 API, не имеют параметров, указывающих цвет или толщину линии. Такие параметры хранятся в контексте отображения.

Приложение может создать контекст отображения не только для окна приложения, но и для любого другого графического устройства вывода, например, для принтера. В последнем случае оно может рисовать на принтере различные изображения, используя те же функции, что и для рисования в окне приложения.
Можно создать контекст отображения для метафайла. Метафайл — это обычный файл или файл в памяти, в котором хранятся последовательности команд интерфейса GDI. Приложение может выполнять графический вывод в метафайл как в обычное устройство вывода, а затем «проигрывать» метафайл на реальном устройстве вывода.
Контекст устройства в терминах ОС Microsoft Windows выступает в роли связующего звена между приложением и драйвером устройства и представляет собой структуру данных размером примерно 800 байт. Эта структура данных содержит информацию о том, как нужно выполнять операции вывода на данном устройстве (цвет и толщину линии, тип системы координат и т. д.).

Если приложение получает или создает контекст для устройства отображения, такой контекст называется контекстом отображения (display context). Поэтому когда, например, приложение получает контекст для отображения в одном из своих окон, такой контекст называется контекстом отображения. Если же ему требуется выполнять операцию вывода для устройства (для принтера или для экрана дисплея), приложение должно получить или создать контекст устройства (device context). Следует понимать, что контексты устройства и отображения содержат описания одних и тех же характеристик и имеют одинаковую структуру. Название контекста определяется только тем, относится ли контекст к окну отображения или устройству вывода.

Концепция графического интерфейса GDI+ несколько отличается от концепции «классического» графического интерфейса GDI, с которым привыкли иметь дело разработчики приложений Microsoft Windows. Прежде всего, это касается класса Graphics, реализующего в себе как свойства контекста отображения, так и инструменты, предназначенные для рисования в этом контексте. Для того чтобы приложение могло что-нибудь нарисовать в окне, оно должно, прежде всего, получить или создать для этого окна объект класса Graphics. Далее, пользуясь свойствами и методами этого объекта, приложение может рисовать в окне различные фигуры или текстовые строки.

На интернете существуют немало уроков по программированию с GDI+. Новинки не трудно учатся и ищут багатые возможности такой библиотеки.

\subsection{OGRE (Object-Oriented Graphics Rendering Engine)}
OGRE - объектно-ориентированныйграфический движок с открытым исходным кодом, написанный на C++\cite{OrgeEngine}. Автором OGRE является Стив Стриитинг.
   Ogre имеет следующие возможности:
   \begin{itemize}
  \item поддержка платформ Windows,Linux и Mac OS X;
 \item скриптовая система управления материалами (мультитекстурирование, мультипроходное смешивание);
 \item загрузка текстур в формате PNG, JPEG, TGA, BMP или DDS, также поддержка сжатых текстур (DXT/S3TC);
 \item экспортеры для основных коммерческих и свободных пакетов 3D моделирования;
 \item система управления ресурсами;
 \item поддержка Direct3D, OpenGL;
 \item поддержка шейдеров, написанных на ассемблере или языках высокого уровня: Cg.
   \end{itemize}


\subsection{IRRLICHT ENGINE}
Irrlicht Engine является кросс-платформенным высокую производительность двигателя реальном времени 3D написана на C ++ \cite{IrrlichtEngine}. Он оснащен мощным высокого уровня API для создания полной 3D-и 2D-приложений, таких как игры или научной визуализации. Он поставляется с отличной документацией и интегрирует все современное состояние функций для визуального представления, такие как динамические тени, системы частиц, анимация персонажей, крытые и открытые технологии, и обнаружением коллизий. Все это доступно через хорошо разработаны C++ интерфейс, который очень прост в использовании.
Irrlicht Engine имеет основные функции:
\begin{itemize}
\item высокая производительность реальном времени 3D-рендеринга использованиемDirect3D и OpenGL 
Платформа независимой . Работает на Windows, Linux, OSX, Solaris и другие.
\item огромные встроенной и расширяемой библиотеки материалов с вершинные, пиксельные и геометрических шейдеров поддержки
\item бесшовные крытый и открытыйсмешивания через высоко настраиваемый управления сценой
\item анимация персонажей система скелета и морфинг целевой анимации
\item эффекты частиц, рекламные щиты, световые карты, отображение окружающей среды , трафарет буфера теней , а также множество других специальных эффектов
\item несколько языковых привязок, которые делают двигатель доступными для других языков, таких как C \#, Visual Basic, Delphi, Java ...
\item две платформы и драйверов независимых быстрой визуализации программного обеспечения включены. Они обладают различными свойствами (скорость против качества) и функция все необходимое: перспективы правильного отображения текстур, билинейная фильтрация, к югу правильности пикселей, Z-буфера, Затенение Гуро, альфа-смешения и прозрачность, быструю 2D-чертежей и многое другое
\item мощный, настраиваемый и простой в использовании графический интерфейс 2D-системы с кнопки, списки, поля редактирования,
2D функции рисования, как альфа-смешения, цвет ключа на основе блитирования, шрифт рисунок, и смешивание 3D с 2D-графики
\item чистый, легко понять, и хорошо документированный API с большим количеством примеров и учебников
\item написанная в чистом C + + и полностью объектно-ориентированным
\item прямой импорт из общей сетки форматы файлов: Maya (объект)., 3DStudio (.3 DS), COLLADA (DAE)., Blitz3D (B3D.), Milkshape (ms3d.), Quake 3 уровня (BSP)., Quake2 моделей (. md2), Microsoft DirectX (. Х)
\item прямой импорт текстур: Windows Bitmap (BMP.), Portable Network Graphics (PNG.), Adobe Photoshop (PSD)., обмена файлами JPEG форматы (JPG)., Truevision Targa (TGA)., ZSoft Painbrush (PCX)
\item быстрое и легкое обнаружение столкновения и ответа
\item оптимизирован быстрая 3D математикии библиотеки контейнер шаблонов
\item оптимизирован быстрая 3D математикии библиотеки контейнер шаблонов
\item непосредственно чтение (сжатый) архивов. (ZIP.,. Пак,. Pk3,. NPK)
\item встроенный быстрый парсер XML 

\end{itemize}

Двигатель с открытым исходным кодоми совершенно бесплатно.
\subsection{Оценка существующих решений}
Для оценки существующих решений рассматриваются следующие критерия:
\begin{itemize}
\item Исходный код. Сегодня почти все программисты игр используют библиотеки с открытым кодом. Это позволяет программистам быстро создать приложение. Кроме того опытные программисты могут развивать используемую библиотеку на высшую версию.  Исходный код --- важнейший компонент для процесса портирования программного обеспечения на другие платформы. Без исходного кода какой-либо части ПО портирование либо слишком сложно, либо вообще невозможно.
\item Работа с сетью. Визуализация не только в виртуальном мире, но и в сети-Интернете. Модель сервер-клиенты создается для удобного использования приложения через Интернет.
\item Возможность создания эффектов. При визуализации очень нужны эффекты: эффект тени, эффект воды, эффект степени размытия движения, эффект высококачественных текстур, эффект освещения и т.д. С помощью перечисленных эффектов визуализация поведения агентов будет эффективна и красива.
\item Работа с графикой 3D. В программе практики визуализация поведения агентов будет на 3D, потому что на 3D будет реально чем на 2D.
\item Платформа --- Всякое приложение работает на одной определенной платформе или на несколько определенных платформ. Если приложение работает на многих платформ, то оно популярно используется, чем другие приложения, работающих на малых платформ.
\end{itemize}


\begin {table} [h]
	\label {table:GraphicsValues}
	\caption {Таблица оценки работы с графикой}
	\begin {tabularx} {\linewidth} {|c|X|X|X|X|}
		\hline
			Средства				& 	Карты нормалей		&  Бамп мэппинг		&	Вершинная анимация	&	Скелетная анимация		\\
		\hline
			OpenGL и Direct3D	&		+					&		+				&		+						&		+							\\
		\hline
			Библиотека GDI+	&		-					&		+				&		-						&		-							\\
		\hline
			OGRE					&		+					&		+				&		+						&		+							\\
		\hline
			Irrlicht Engine			&		+					&		+				&		+						&		+							\\
		\hline
		
	\end {tabularx}
\end {table}

\begin {table} [h]
	\label {table:EffectsValues}
	\caption {Таблица оценки оценки возможности создания эффектов}
	\begin {tabularx} {\linewidth} {|c|X|X|X|X|X|}
		\hline
			Средства				& 	Эффект тумана	&  Анимация водных поверхностей	&	Динамические тени	&	Прозрачные объекты 	& Объемное освещение\\
		\hline
			OpenGL и Direct3D	&		-				&		+									&		+					&		+						&		+					\\
		\hline
			Библиотека GDI+	&		- 				&		-									&		-					&		+						&		+					\\
		\hline
			OGRE					&		+				&		+									&		+					&		+						&		+					\\
		\hline
			Irrlicht Engine			&		+				&		+									&		+					&		+						&		+					\\
		\hline
		
	\end {tabularx}
\end {table}

\subsection{Выводы}
     На основе результатов анализа достоинства и недостатки существующих средств разработки модуля, были сделаны выводы:
     
 \begin{itemize}
\item Существует немало средств для разработки модули и найденные аналоги популярны в области компьютерных графических приложениях.
\item Движки ORGE, Irrlicht Engine и Havok широко испльзуют для разработки больших графических игр. Можно использовать стандартные модели, которые находятся в их туториалях или создать другие.  
\item При использовании движков программисты мало пишут, но результаты могут большими.
\item Библиотека GDI+ часто используется в 2D графических приложениях, но в в 3D графических приложениях невозможно.
\item Irrlicht Engine поддерживает 6 API для рендеринга: Direct3D 8.1, Direct3D 9.0, OpenGL 1.2-3.x, программный рендерер Irrlicht, программный рендерер Burningsvideo,null device, поэтому при использовании такого движка программист может  выбрать один из API по характеру приложения.
     \end{itemize}

В рамке разработанной модули выбран движок Irrlicht Engine для реализации. Движок участвует в модуль как один рендеринг-компонент.

\section{Требования к системе визуализации}
Функциональные требования системы:

\begin{enumerate}
\item Физические свойства агента: координаты, скорость (линейная), ускорение

\item Состояние приводов: проигрывание анимации соответствующей состоянию привода агента

\item Отладочная информация: нарисовать примитив или вывевести текст.
\end{enumerate}

\section{Выводы}
В первой главе были иследованы следующие проблемы:
\begin {itemize}
\item Термины мультиагентных систем(МАС), классификация МАС и применения МАС в различных областях, особенно в графических компьютерных приложениях.
\item Анализированы существующие системы, которые используются для моделирования поведения агентов.
\item Анализ вывод о способах визуализации поведения ИА.
\item Анализированы существующих средств для разработки модули. На основе выбран Irrlicht Engine с помощью таблиц оценок критериев средств для реализации модули.
\end {itemize}

Анализирование существующих систем моделирования ИА показывает, что бывают недостатки при визуализации поведения ИА. В первых, все системы разработались на 2D, действие и модели ИА довольно простыми (кроме MASON, разработанной на 2D и 3D). Простые модели ИА на 2D графике перемещаются по виртуальному миру без анимации. Во вторых пользователи при их использовании должны фокусировать на 2 части: на модели агента и на отладочную информацию. Это потеряет много времени при отладке сложных системы ИИ.

Анализ способов визуализации позволяет сделать вывод, что скелетная анимация, выполняется с большей производительностью, чем вершинная и является более предпочтительной для визуализации поведения интеллектуальных агентов.

\chapter{Разработка модели, метода и алгоритмов визуализации поведения ИА в компьютерных играх}
\section{Архитектура модуля визуализации поведения ИА}
Модуль построен тремя уровнями: пользовательское представление, программное представление и уровень реализации. Архитектура модуля визуализации поведения ИА представлена на рисунке \ref {figure:Architecture}
Модуль реализован с использованием  среды программирование и игрового движка, подробно в разделе 
\ref{chapter:Design}, на основе мультиагентного подхода.
\begin {figure}[h]
	\includegraphics[width=\columnwidth] {systemcomponentvisual2.png}	
	\caption{Архитектура модуля визуализации поведения ИА}
	\label {figure:Architecture}
\end {figure}

Пользовательское представление (view level)  рассматривает доступ пользователя к информации, как и к возможным операциям, так и в контексте инфоструктуры, отображаемой пользователю. Этот этап содержит интерфейсы, на которые пользователь воздействует.


На уровне программного представления описаны объекты, которые существуют в модули. Включаются на этом этапе объект (пассивныеобъекты) и ИА. Как показано на рисунке \ref {figure:Architecture} объекты в виртуальном мире имеют физическая модель и компонент визуализации. ИА имеет наиболее компонентов, чем пассивный объект. Они имеют ещё модель поведения.

Уровень реализации состоит из трех компонентов: алгоритмы ИИ, симуляция физиуи и движок Irrlicht.

В \cite{threeDSimulation} показана архитектура для визуализации  поведения ИА на основе 3D графики.

\section{Разработка алгоритмов поведения ИА \label{section:Pathfinding}}

Уровень реализации включает в себя представление виртуальной среды, планирование агента пути и навигацию по всему моделирования. Виртуальная среда представляется с помощью оснащенного четырехъядерного дерева. Планирования пути и предупреждение столкновения выполняются с использованием алгоритма поиска кратчайшего пути A*  и алгоритма управления поведением (Steering Behaviors)\cite{SteeringBehavior, a-star-for-AI}.

В компьютерных играх широко используется алгоритм А-звезды (A-star) для поиска поиска кратчайшего пути между двумям позициями на карте\cite{a-star-for-AI}. Если в игре имеются большие размеры карты, то время выполнения поиска пути велико. Поэтому нужно оптимировать алгоритм поиска. Для этого необходимо разбить карту на области, у которых имеются небольшие размер, для уменшения количества узлов на карте.
На рисунке \ref{figure:AStar} представлен пример поиска от точки А до B по карте с помощью алгоритма A-star.
\begin {figure} [h]
	\includegraphics[width=\columnwidth] {astarFigure.pdf}
	\caption {Пример поиска от точки А до B по карте с помощью алгоритма A-star}
	\label {figure:AStar}
\end {figure}
Для реализации этого алгоритма нам необходимо ввести несколько понятий и переменных:
\begin{itemize}
\item	узел — По сути это одна клетка. Можно было также ее назвать точка или вершина. Содержит координаты, G. H, F, родительский узел.
\item	родительский узел — узел из которого произошел переход в текущий узел
\item	открытый список — в этот список добавляются все узды, которые необходимо проверить
\item	закрытый список — в этот список добавляются узлы, которые проверять не нужно
\item	G — стоимость передвижения из одного узла к другому. Если узел по диагонали к другому то стоимость будет равна 14, если же по горизонтали или вертикале то 10
\item	H — эвристическое значение расстояния от текущего узла до конечного (только по вертикали или горизонтали, и не учитываются преграды на пути)
\item	F — сумма G и H, значит F = G + H.
\end{itemize}

Пошаговое представление алгоритма A-Star:


\begin{algorithm}
\caption{Алгоритм А-звезды}\label{AstarsAlogorithm}
\begin{algorithmic}[1]
\Procedure{Astar}{$start,goal$}\Comment{Start - начальная позиция, goal - целевая позиция}
\State $closedset \gets \emptyset $
\State $openset \gets \lbrace start \rbrace$
\State $pathmap \gets \emptyset$
\State $start.g  \gets 0$
\State $start.h \gets heuristiccostestimate(start, goal)$
\State $ start.f \gets start.g + start.h$
\While{$openset \not= \emptyset$}

\State $x \gets {v:v \in openofset, f(v) = min}$
\If {$x = goal$} 
\State \textbf{return} $reconstructpath(start,goal)$
\State $ openset \gets openset - x$
\State $closedset \gets closedset + x$
\ForAll {$y \in neighbor_nodes(x)$}
 \If{$ y \in closedset$}
    $continue$
 \EndIf
\State    $tentativegscore  \gets x.g + distbetween(x,y)$

\If {$y \not \in openset$}
\State $openset \gets openset + y$
\State $tentativeisbetter \gets true$
\Else 
 	\If{$ tentativegscore < y.g  $}
 	\State $tentativeisbetter \gets true$
 	\Else 
	 \State $tentativeisbetter \gets false$
 \EndIf
\EndIf
\If{$tentativeisbetter = true$}
 \State $ y.came_from \gets x$
 \State $ y.g \gets tentativegscore$
\State $ y.h \gets heuristiccostestimate(y, goal)$
\State $ y.f \gets y.g + y.h$
 \EndIf
 \EndFor

\EndIf
\EndWhile
\State \textbf{return} $failure $
\EndProcedure
\end{algorithmic}
\end{algorithm}


Далее заполняется карта $pathmap$. Путь можно проследить только от целевой вершины к старту. Используется алгоритм \ref{FillMappath} для заполнения карты.

\begin{algorithm}
\caption{Алгоритм для заполнения карты}
\label{FillMappath}
\begin{algorithmic}[1]
\Procedure{reconstructpath}{$startnode, goalnode$}
\State $currentnode \gets goalnode$
\While{$currentnode \not= NULL$}
\State $pathmap \gets pathmap + currentnode$
\State $currentnode \gets currentnode.camefrom$
\EndWhile 
\EndProcedure
\end{algorithmic}
\end{algorithm}

Поиск кратчайшего пути является отдельным классом. Когда агент нужен перемещать  от одной позиции ко другой, то новый экземлятор этого класс запускается. Результат обработки даёт контейнер, содержащий узлы, через которых агент должен проходить.

Управление поведениями было предложено Крейгом Рейнольдсом в докладе <<Управление поведениями отдельных персонажей>>\cite{SteeringBehavior}, сделанном для конференции разработчиков игр. В этом докладе описывается ряд алгоритмов, которые создают систему воздействий, прикладываемых к персонажам, которые используются в играх и симуляциях. Эти воздействия используются, чтобы привести персонажи в движение или изменить направление движения персонажа по мере его перемещения. Они также могут использоваться для симуляции различных поведений групп объектов, например, таких как скапливание (flockling).

Бывают немало поведений агента в определенном виртуальном мире. Несколько из них считают основными. Это значит, что из этих поведений можно разработать разные поведения, соответствующих с конкретной ситуацией. Можно перечислить следующие основные поведения:
\begin {itemize}
\item поиск (seek): Агент пытается передвигаться в определенную точку. Это может быть неподвижная точка, а может быть и другой двигающийся персонаж.
\item избегание (flee): полная противоположность поиску. Агент пытается любыми способами избежать встречи с определенной точкой или другим агентом.
\item прибытие (arrive): почти тоже, что и поиск, но агент по мере приближения к цели замедляет свое движение и полностью останавливается в точке назначения.
\item преследование (pursue): представляет собой усовершенствованный поиск, т.к. принимается во внимание скорость цели. Вместо того, чтобы использовать текущее положение цели для ее поиска, агент использует прогнозируемое положение цели. Очевидно, что это поведение применяется только к движущейся цели.
\item уклонение (evade): полная противоположность преследования. Агент определяет точку, где будет находиться его преследователь, и будет стараться покинуть эту точку или отдалиться от нее.
\item блуждание (wander): случайное, но гладкое и реалистичное движение агента. 
\item избегание препятствий (object avoidance): Агент видит препятствия на своем пути и огибает их.
\item следование по маршруту (path following):  Агент прилагает все усилия, чтобы остаться на данном пути, но делает это реалистично (в соответствии с законами физики).
\end {itemize}
3D визуализация - компонент используется для отображения результатов моделирования агентов в виртуальной среде в определенный момент времени. В результате разработки системы этот компонент обновляется через короткое определенное время и отображается с помощью картинки, привязанной к агенту. 

Работа агента в виртуальном мире отражена в алгоритме \ref{algorithm:agentWorkinWolrd}.

\begin{algorithm}
	\caption{Алгоритмы работы агента в виртуальном мире}
	\label{algorithm:agentWorkinWolrd}
	\begin{algorithmic}
	\Function {Work} {$listEntities, target$}
		\ForAll{$a \in listEntities$} 
        \If{$(a.Position - target.Position)^{2} < maxSeeLength^{2}  \& target.selection = false$}
     \State $a.behavious \gets Arrival$
     \EndIf
     \If {$a.Position = target.Position$}
     \State $a.Behavious \gets Attack$
     \State $TimeAttack \gets 0$
       \EndIf
       \If {$ TimeAttack > MaxTimeAttack$}
       \State $a.Behavious \gets Selection$
       \State $target.seletion \gets false$
       \State $a.Behavious \gets GoHome$
       \Else
       \State $ a.Behavious \gets Wander$
       \EndIf
        \State $a.Update(dt)$
       \If {$a.Position = home.Position$}
       \State $a.Behavious \gets Wander$
       \EndIf
		\EndFor
	\EndFunction
	\end{algorithmic}
\end{algorithm}

\section{Разработка модели визуализации и модели агента}

Модель визуализации состоит из трех компонентов:
\begin{itemize}
\item меш –  это набор вершин и многоугольников, определяющих форму трёхмерного объекта. Это физический объект в виртуальном мире.
\item анимация - последовательность сменяющих друг друга кадров. С её помощью показывается то, что агент выполняет действия в виртуальном мире.
\item отладочные информации. Это содержатся координаты агента, направление движения, направление поиска, текущее действие (<<думать>>, поиск, подбор, возврат и т.д.).
\end{itemize}

Реакция объектов виртуального мира на события и их активное поведение реализуется в поведенческой модели. Пассивные объекты не имеют поведенческой модели, их реакция на столкновения с другими объектами полностью определяется их физическими свойствами. Поведение интерактивных объектов не является интеллектуальным и представляет собой статически запрограммированные реакции на столкновение или использование другими объектами. Активные объекты виртуального мира, как например, персонажи, являются автономными агентами. Структура поведения агента представляется следующим образом:

\begin{equation}
B = (K_{Logic}, K_{Map}, A_{Path}, S_{Actuators}, M, D_{Debuge})
\end{equation}

где: $K_{Logic}$ --- база знаний агента, содержащая множество фактов и правил логического вывода;

$K_{Map}$ --- карта путей, которая используется для решения задачи навигации;

$A_{Path}$ --- алгоритм поиска оптимального маршрута;

$S_{Actuators}$ ---  множество эффекторов (манипуляторов) агента;

$M$ ---  очередь сообщений агента;

$D_{Debuge}$ --- отладочные информации.

Взаимодействие между компонентами агента представлено на рисунке \ref{figure:AgentStructures}  в соответствии с нотацией, используемой в работе Рассела и Норвига:

\begin {figure}[h]
\caption {Структура агента}
\label {figure:AgentStructures}
\includegraphics[width=\columnwidth] {AgentStructure.pdf}
\end {figure}

\section{Модель виртуального мира}
Виртуальный мир любой игры состоит из множества областей или локаций и объектов размещенных в локациях. Например, виртуальный мир шахмат состоит из одной области(доска) и 32 объектов(фигуры). Структура виртуального мира игры в общем случае выглядит следующим образом:
\begin{equation}
W = (S_{areas}, S_{objects})
\end{equation}

где: $(S_{areas}$  ---  множество областей;

$S_{objects}$ --- множество объектов.
 
Каждый объект виртуального мира в свою очередь представляется как структура:

\begin{equation}
E = (P, B)
\end{equation}
где: $P$ --- физическая модель;

$B$ --- модель поведения.

Модель поведения B описывает реакцию объекта на столкновение с другими объектами и поведение объекта во время итерации игрового цикла. Виртуальный мир игры состоит из активных и пассивных объектов. Для моделирования поведения активных объектов используется мультиагентный подход, в дальнейшем активные объекты будем называть агентами.

Модель  поведения  использует  данные  физической  модели  для  принятия решений и навигации. Алгоритмы Steering Behavior оперируют данными физической модели. Тогда физическая модель P описывает свойства, определяющие поведение объекта в динамике, такие как:
\begin {itemize}
\item геометрия;
\item  координаты;
\item  скорость;
\item  угловая скорость;
\item  ускорение;
\item  угловое ускорение;
\item  масса
\item  сила на объект
\end {itemize}
\section{Разработка метода синхронизации компонентов модели визуализации}

Все объекты виртуального мира представляются как композиты графической, физической и поведенческой модели. Пассивные объекты не имеют поведенческой модели. Структура активного объекта (агента) можно представляться таким образом:
\begin{center}
Agent = (графический компонент, физический компонент, AI-компонент)
\end{center}

Графичекий компонент использует данные физическоно компонента, которые обработанны AI компонентом для рендеринга на сцене. Такими данными являются новые координаты, новое состояние каждого манипулятора агента и примитивы отладочные информации.

AI компонент используется данные физического компонента для принятия решений и навигации. Такой компонент используется для моделирования поведения активных объектов и в дальнейшем активный объект имеет «интеллект». Агент имеет знания о виртуальное среде (состояние среды, состояние и поведения других агентов в среде). AI компонент анализирует такие знания и обрабатывает их. В AI компоненте были разработаны алгоритмы обработки события мира и алгоритмы управления поведения ИА.

Физический компонент сохраняет все физические параметры агента в виртуальном мире. Была разработана синхронизация физического и AI компонентов.

\section{Выводы}

Таким образом, были разработаны:
\begin{itemize}
\item алгоритм визуализации поведения ИА на основе мультиагентного подхода
\item формальные модели, описывающие структуру вирутального мира игры, визуализации и агентов
\item  разработка механизма взаимодействия между ИА
\item интерфейс взаимодействия компонентов поведения агента, реализующих специфические задачи ИИ.
\item алгоритм поиска кратчайшего пути А-звёзды и алгоритмы управления поведениями агентов.
\end{itemize}

% Глава 3
\chapter{Проектирвание модуля визуализации поведения интеллектуальных агентов\label{chapter:Design}}
\section{Функциональная структура системы}
В соответствии с предъявленными требованиями была разработана функциональная структура системы. Система должна предоставлять функции, которые отображены на диаграмме прецедентов, рисунок ~\ref{fig:usecases}

\begin{figure}[h]
%COMMENT: У рисунка очень большие поля и много пустого места (см. usesphu.pdf)
\includegraphics[width=\columnwidth]{useCasePhu.png}
\caption{Use Case диаграмма}
\label{fig:usecases}
\end{figure}
\section{Выбор инструмента для реализации программы}
Как показано в первой главе, инструмент для реализации программы был выбран игровой движок Irrlicht (Game Engine Irrlicht) потому что движок Irrlicht адаптирует многие платформы: Windows, Unix, OSX  и т.д.
При работе с игровым движком Irrlicht используется прорамма IrrXML для работы с файлами.

\section{Выбор вида анимации}
Одним из преимуществ использования Irrlicht в том, что он поддерживает форматы файлов, что почти любой 3D программного обеспечения может производить.
Движок Irrlicht поддерживает многие виды файла сохранения модели для анимации:
\begin {itemize}
	\item B3D файлы(.B3D)
     \item MicrosoftDirectX (. х)
	\item Milkshape (. ms3d)
	\item Quake 2 модели (. md2)
	\item Quake 3 модели (. md3)
\end {itemize}

Рассмотрим последовательно эти форматы файлов на основе их архитектуры.В туториале Irrlicht\cite{chaperIrrlichtFile} представлены форматы файлов, поддерживающих в движке Irrlicht.

Microsoft DirectX (. х) -  формат файла для хранения 3D объектов, созданный компанией Microsoft.Этот формат хранит информацию о геометрии 3D объекта (координаты вершин и координаты нормалей), текстурные координаты, описание материалов, пути и названия к текстурам, которые используются. Хранится иерархия объектов, хранится анимация, и хранятся привязки вершин к «костям» с описанием весов. В X файле может отсутствовать какая-либо информация об объекте (например в X файле могут содержаться только координаты вершин).

X файл может быть текстовым либо бинарным. Анимация может быть сохранена как в виде скелетной анимации, так и в виде трансформации вершин.

Milkshape (. Ms3d) – Формат файла для сохранения 3D объектов с анимацией. Такой формат файла экпотируется из компьютерной программы MilkShape 3D, которая была разработана Митом Кириганом в 1996 году. В основном, MilkShape 3D используется при моделирования объектов для компьютерных игр Half-Life, Blockland, The Sims 2, The Sims 3 и других sandbox-игр. Возможности для экспорта моделей в редакторе были значительно расширены его создателем и сообществом, которое образовалось вокруг редактора. Поэтому, на данный момент, в MilkShape присутствует множество плагинов для экспорта трёхмерных моделей в различные игровые форматы. Анимация движений в редакторе проводится с помощью скелетной анимации. Это позволяет экспортировать анимационные объекты в форматах файлов для таких игр какQuake, Half-Life, Genesis3D, Unreal и др. Поддерживаемые форматы для экспорта объектов включают в себя все основные игровые движки: Source, Unreal Engine, id Tech, Lithtech.

Формат моделей Quake 2 .md2 - Формат использовавшийся в линейке игр Quake 2. Отличается крайней простотой в реализации при наличии анимации и достаточно невысоком размере. Анимация производится путём трансформации вершин от кадра к кадру (морфинг). Анимация в md2 формате представлена набором ключевых кадров, каждый из которых задаёт позиции вершин, индекс нормали освещения “к вершине”, и дополнительные параметры, такие как: имя кадра, растяжение и смещение. Последние имеют место в связи с тем, что вершны хранятся в 8 битном формате для уменьшения количества памяти под кадр, а эти параметры позволяют достаточно успешно справиться с погрешностями.

Формат моделей Quake 3 .md3  является моделью формат, используемый в движке Quake 3, а также в его многочисленных модификациях. Этот формат используется в основном для модели игроков и неструктурные геометрию (не статических моделей), хотя она может быть использована для структурных целей. Формат не поддерживает скелетной анимации . Вместо этого, анимации сохраняются на каждой вершине основе. 

В таблице \ref {table:IrrlichtFileFormats}. поддерживает информацию о форматах Irrlicht файл анимации.

\begin {table}
	\caption {Форматы анимаций, поддерживаемые Irrlicht}
	\label {table:IrrlichtFileFormats}
\begin {tabularx} {\linewidth} {|c|X|X|X|}
\hline Форматы & Основное описание & Скелетная анимация & Morph-анимация \\
\hline B3D файлы (. B3D) & Blitz 3D представляет собой легкий формат построен BlitzBasic компании & Да & Нет \\
\hline MicrosoftDirectX (. х) & . Х 3D формате Microsoft, построенный на Direct X SDK. Формат доступна как в бинарном виде и человеческого восприятия форме текста & Да & Нет \\
\hline Milkshape (. Ms3d) &  & Да & Нет \\
\hline Quake 2 модели (. Md2) & Файлы очень мало и, следовательно, нагрузка очень быстро в сцене. Сетки очень легкие и эффективные. & Нет & Да \\
\hline
\end {tabularx}
\end {table}

Файл с форматом Quake 2 модели (. Md2) загрузится очень быстро и поддерживает морфинг-анимации. Геймдизайнер имеет больше контроля над движениями, потому что он может определить отдельные позиции из вершин в ключевой кадр, а не ограничиваться скелетов. Это может быть полезно для анимации ткани, кожи и выражения лица, потому что это может быть трудно, чтобы соответствовать те вещи, к костям, которые необходимы для скелетной анимациию.
Поэтому было принято решение использовать морфинг-анимацию для визуализации поведения интеллектуальных агентов.
 
\section{Выбор языка программирования.}
В качестве среды разработки была выбрана среда MS Visual Studio 2010, языком разработки был выбран язык C++. Выбор языка и платформы обусловлен высокой скоростью разработки приложений, приемлемой скоростью выполнения исполняемого кода.
	
\section{Выбор форматов файлов для сохранения данных}

Сохранение состояния игры и загрузка сохранённых состояний --- это обычная, необходимая для многих игр процедура. Существует немало способов сохранения и загрузки данных:
\begin{enumerate}
\item сохранение данных в бинарный файл.

 Плюсы бинарного режима:
 \begin{itemize}
\item возможность сэкономить на памяти и стандартизировать требования к её размерам; 
\item возможность сохранять произвольные разнородные данные простой запись куска памяти.
 \end{itemize}
Минусы: 
\begin{itemize}
\item возможность потратить память (например, если сохраняемые числа в диапазоне [0..999] для int) и полностью утратить возможность к стандартизации (разные архитектуры и платформы);
\item невозможность сохранять данные простой записью куска памяти (разный порядок байт внутри переменной в зависимости от архитектуры, выравнивания и полный хаос со структурами, беготня, спотыкания и ещё большая непереносимость с директивами \#pragma pack; адресация членов объекта через указатели, приводящая к необходимости написания отдельных методов его сохранения).
\end{itemize}

\item Сохранение данных в текстовый файл. Текстовой файл сохраняет базу данных, которая имеет простую структуру и небольшой размер.Использование текстовых файлов для хранения баз данных имеет несколько неоспоримых преимуществ перед более сложными альтернативами, такими как DBM-файлы или системы управления большими базами данных типа Oracle и Sybase. Ниже перечислены некоторые из основных преимуществ текстовых файлов.
\item Сохранение данных в SQL. Часще всего SQL используют для сохранения большей базы данных, в которых содержится много таблиц, записей, например для сохранения данных Веб-страницы. SQL редко используется для сохранения данных игры из-за низкую гибкость.
\item Сохранение  данных в файл с форматом XML
\end{enumerate}

Базы данных, хранящиеся в текстовых файлах, являются переносимыми. Их можно без всяких проблем использовать практически на любой компьютерной платформе.

Текстовые файлы можно редактировать с помощью обычного текстового редактора, а также распечатать на бумаге без привлечения каких-либо специальных средств.

Текстовые файлы баз данных очень просто создавать, а также вносить в них первоначальные данные.

Текстовые файлы баз данных могут быть легко импортированы в программы электронных таблицы, текстовые процессоры или СУБД. Практически все известные приложения могут импортировать данные, хранящиеся в текстовых файлах.

Но из-за того, что вставка записей в середину текстовой базы данных — довольно медленная и не лишенная ошибок операция и  при сбое в момент перезаписи файла может произойти частичная или полная потеря данных, файл с форматом .txt тоже мало используется при сохранения данных игры.

Был выбран способ сохранения данных в файл с форматом XML. XML используется для хранения конфигурации игры, хранения уровней игры. Этот формат легко менять, в него легко добавлять нужные данные, причём, только там, где они реально нужны, его легко читать и легко записывать. Он так же может помочь для создания сейвов игры.

Файл для сохранения конфигурации виртуального мира в формате XML будет иметь следующую структуру:
\lstset{language=XML}
\begin{lstlisting}
<?xml version="1.0"?>
<config>
   <!-- This is a config file for windows of game -->
   <terrain file="../DataGame/DataImage/terrain-heightmap.bmp" />
   <sizewindow width="The width of the game window"  height="The height of the game window" />
   <sizemap width1="First width game card game" width2 = "Second width game card game"/>
   <texture text1 = "The first texture for coloring the world"
 	     text2 = "The second texture for coloring the world"
         textnN = "The N texture for coloring the world"/>
</config>
\end{lstlisting}


При выходе из приложения состояние ИА сохранено тоже в файл XML. Был сохранены координаты, поведение, линейная скорость, масса. Этот файл
будет иметь следующую структуру:
\begin{lstlisting}
<?xml version="1.0"?>
<save>
<!--Player 1-->
	<Player 1>
		<Position X="Position of a first agent"/>
		<Angle X="The current angular rotation of a first agent"/>
		<Mass value="Weight of a first agent"/>
		<Velocity X="Current speed of a first agent"/>
		<Behaviour value="Current behavior of a first agent"/>
		<Energy value="Energy of a first agent"/>
	</Player 1>
<!--Player 2-->
	<Player 2>
		<Position X="Position of a second agent"/>
		<Angle X="The current angular rotation of a second agent"/>
		<Mass value="Weight of a second agent"/>
		<Velocity X="Current speed of a second agent"/>
		<Behaviour value="Current behavior of a second agent"/>
		<Energy value="Energy of a second agent"/>
	</Player 2>
........
<!--Player N-->
	<Player N>
		<Position X="Position of the n-th agent"/>
		<Angle X="The current angular rotation of the n-th agent"/>
		<Mass value="Weight of the n-th agent"/>
		<Velocity X="Current speed of the n-th agent"/>
		<Behaviour value="Current behavior of the n-th agent"/>
		<Energy value="Energy of the n-th agent"/>
	</Player N>
</save>
\end{lstlisting}

\section{Процесс проектирования}
\subsection{Классы реализующие модель агента}
На рисунке \ref{image:AgentClasses} представлены C++ классы, соответствующие моделям агента. Класс GameObject служит базовым классом для модели агента. Он состоит из трех классов: PhysicsComponent, GraphicsComponent и AIComponent. В методе update класса  GameObject реализуется управление действиями объекта через определенное время $dt$.

При создании объекта класса GameObject вызывается метод connectWithPhysic класса AIComponent  для соединения с классом PhysicsComponent. В даньнейшем объект класса вызывает методы класса PhysicsComponent для обновления нового состояния агента. Метод Update класса AIComponent вызывается при обновлении состояния агента.

Аттрибут mText класса GraphicsComponent содержит отладочные информации. Соответственно метод getDebugData возвращает строку, содержащую отладочные информации – параметры о агенте.

Метод thinking класса  AIComponent  необходимо перегрузить, если требуется добавить объекту реакцию на столкновение с другими объектами. А метод Bounce перегрузит, если требуется добавить объекту реакцию на столкновение с краем карты.

\begin {figure}[h]
\includegraphics[width=\columnwidth]{picture.pdf}
	\caption {Диаграмма классов. Классы реализующие модель агента}
	\label{image:AgentClasses}
\end {figure}

\subsection{Классы реализующие поведения модели агента}
На рисунке \ref {image:AgentClassess} представлены C++ классы, соответствующие моделям агента. Класс ISteering служит базовым классом для модели поведения всех
объектов игры. Этот класс является абстрактным.
Классы реализующие поведения наследуют от абстрактного класса ISteering описаны подробно в таблице \ref {table:AgentClasses}.
\begin {figure}[h]
\includegraphics[width=\columnwidth]{picture2.pdf}
	\caption {Диаграмма классов. Классы реализующие поведения агетов}
	\label{image:AgentClassess}
\end {figure}

\begin{table}
\caption{\label{table:AgentClasses}Описание классов реализующие поведения агента}
\begin{center}
\begin{tabularx}{\linewidth}{|c|X|X|X|X|}
\hline
Класс & \multicolumn{3}{|c|}{\textbf{Метод}} & Наследует от какого класса \\
\hline
 & Название & Возвращение  & Входные параметры & \\
\hline
Seek  & Init() & Bool & Vehicle : IVehicle*
Target : vector3df & ISteering\\
\hline
Seek  & getSteering() & Vector3df & нет & ISteering\\
\hline
 Pursuit  & Init()	& bool	& Vehicle : IVehicle*
Target : IVehicle*	&ISteering\\
\hline
 Pursuit  & getSteering()	& Vector3df	& нет	&ISteering\\
\hline
Wander	 &	Init()&		bool&		Vehicle : IVehicle*	&	ISteering\\
\hline
Wander  & getSteering() & Vector3df & нет & ISteering\\
\hline
Avoid	 &	Init()	&bool	&Vehicle : IVehicle*	&ISteering\\
Avoid	 &	getSteering()	&Vector3df	&нет	&ISteering\\
\hline
Arrive	 &	Init()	&bool&	Vehicle : IVehicle*
Target : IVehicle* deceleration :Deceleration&
	ISteering\\
\hline
Arrive  & getSteering() & Vector3df &нет & ISteering\\
\hline
Flee  & Init()	&bool	&Vehicle : IVehicle*
Target : IVehicle*	&ISteering\\
\hline
Flee  & getSteering()&	Vector3df	&нет&ISteering\\
\hline
ArrivalSteering  & Init()&	bool	&Vehicle : IVehicle*
Target : IVehicle*
Distance : float&	ISteering\\
\hline
ArrivalSteering & getSteering()&	Vector3df	&Нет& ISteering\\
\hline
\end{tabularx}
\end{center}
\end{table} 
\section{Архитектура системы}
На рисунке \ref {image:bdSystems} представлена архитектура системы. Входные данные сохраняются в базе данных в формате файла XML. Модуль работы с файлами выполняет разбор файла и передает данные в модуль построения сцены. 

Модуль построения сцены - это основный компонент, преобразующий параметры мультиагентной системы в формат пригодный для работы графической библиотеки. Эта подсистема содержит алгоритмы обработки данных, алгоритмы управления поведения ИА (Steering Behavior) и алгоритм поиска кратчайшего пути. 

Система рендеринга – это компонент для рисования сцены. Такой компонент может быть реализован различными средствами: с помощью низкоуровневого графического API (DirectX, OpenGL, GDI++) или высоковневых графических и игровых библиотек (ORGE, Havok, Irrlicht Engine).

\begin {figure}[ht!]
\includegraphics[width=\columnwidth]{componentSystems.png}
	\caption {Диаграмма компонентов. Архитектура системы}
	\label {image:bdSystems}
\end{figure}

\section{Выводы}
В третьей главе были спроектированы:
\begin{itemize}
\item Функционнальная структура модуля;
\item Выбор инструмента для реализации модуля;
\item Выбор вида анимации, в соответственно был выбран файл для сохранения модели(агента) с форматом .md2;
\item Выбор языка программирования;
\item Выбор формата файла для сохранения конфигурации, параметров виртуального мира и параметров агента;
\item Архитектура системы;
\end{itemize}

Выборы позволяют удобно и быстро создавать модуля и обеспечивает легкость при развитие модуля.

\chapter{Тестирование модуля}
\section{Описание тестового примера}
Спроектирован и реализован прототип системы, моделирующий поведение агентов в трехмерном мире. Прототип протестирован на тестовом примере.
В тестовом примере физика виртуального мира представляется системой абсолютно твердых тел на плоскости. В мире находится множество одинаковых агентов. Агенты могут перемещаться по виртуальному миру. 
Задача агентов: собирать «цветы». Если цветок находится от агента на определенном расстоянии, то агент замечает его и начинает перемещение к цветку. Агент берёт цветок и идет «домой» – в определенную область на карте.
Были разработаны следующие базовые тактики:
\begin {itemize}
\item Избегание препятствий – на пути агента находится препятствие, агент должен найти обходной путь, чтобы не столкнуться с препятствием;
\item Блуждание – агент перемещается по миру в случайном направлении для  поиска цветка;
\item Прибытие – агент при движении в определенную точку постепенно снижает скорость движения и останавливается, когда достигает этой точки;
\item Подбор цветка – агент берёт цветок.
Агенты замечает цель, которая находится в радиусе внимания
\begin{center}
$R_{Attention} = 100$
\end{center}

\end{itemize}

\section{Описание компонента визуализации}
Компонент визуализации привязан к агенту. С помощью программного цикла через промежуточный момент времени dt он обновляется. Компонент визуализации содержит параметры агента: скорость, массу, поведение, координаты, сила воздействующая на агента.
Был спроектирован алгоритм \ref{algorithm:Simulationstep} обновления компонента визуализации.

\begin{algorithm}
	\caption{Шаг итерации моделирования}
	\label{algorithm:Simulationstep}

	\begin{algorithmic}
	\Function {update} {$dt$}
		\ForAll{$a \in listGameObjects$} 
			\State $a.AIComponent.update(dt)$
			\State $a.Position \gets a.Position + a.Velocity * dt$
			\State $a.Velocity  \gets a.Velocity + a.force * dt$
			\State $a.angle \gets a.PhisicsComponent.getAngle()$
			 \State    $a.GraphicsComponent.update(dt)$
			\State  $a.info.update(dt)$           
		\EndFor
	\EndFunction
	\end{algorithmic}
\end{algorithm}

\section{Описание тактик агентов}
Был разработан набор правил, используемый агентами для логического вывода.

Для реализации тестирования модуля, заданы размеры карты. Агенты в процессе работы не могут уйти от границы карты.

\begin{equation}
Withmap1 = Withmap2 = 5000
\end{equation}

Допустим, что время атака цели ИА не более определенного конкретного значения.

\begin{equation}
TimeMaxAttack \leq 8000 (mc)
\end{equation}

%COMMENT: Где расшифровки формул?
Агент идет в случайном направлении, если он не види ни один цветок, не видит препятствие и не предвидит столкновение.
\begin{equation}
Wander = \forall{A}(\overline{seeFlower(X, A)} \bigwedge \forall{B}\overline{seeObstacle(X, B)} \bigwedge \overline{seeBounce(X)}
\end{equation}

Агент выполняет поведение <<атака>>, если он видел любой цветок в виртуальном мире.
\begin{equation}
Attack = \exists{A}(seeFlower(X, A))
\end{equation}

Агент <<видит>> цветок, если расстояние $R_{see}$ до него не более чем 100.
\begin{equation}
seeFlower(X, A) = R_{see} = (X.x - A.x)^{2} + (X.y - A.y)^{2} \leq 100
\end{equation}

При случайном движении агент видит препятствие, если он расстояние $R_{avoidDistance}$ до него не более чем 150.
\begin{equation}
seeThinking(X) =  R_{avoidDistance}  \leq 150
\end{equation}

Агент <<видит>> край, если его координаты удовлетворяют следующим условиям.
\begin{equation}
seeBounce(X) = X.x \geq WithMap1 \bigvee X.y \geq WithMap2 \bigvee X.x \leq 0 \bigvee X.y \leq 0
\end{equation}

Агент <<идёт домой>>, если он придумает о кратчайшем пути и в его руках есть цветок.
\begin{equation}
isGohome(X) = isFindPathToHome(X) \bigwedge isKeeperFlower(X)
\end{equation}

Допустим, что если время атака агента превышает $TimeMaxAttack$:
\begin{equation} 
isKeeperFlower(X) = timeattack \geq TimeMaxAttack
\end{equation}
В таблице ~\ref{table:attacks} приведены описания действий агента в виртуальном мире с описанием воздействия на внешнюю среду.

\begin {table}[h]	
	\caption{Классы действий агента}
	\label {table:attacks}
	\begin {tabularx} {\linewidth} {|c|c|X|}
		\hline
			Действие							& Эффекторы			&	Описание		\\
		\hline
			Wander	& Ноги агента							& 	Выбрать случайную точку двигаться к выбранной точке с помощью действия wander				\\
		\hline
			Arrival								& Ноги агента		& Движение  к  цели  с  использованием  Steering Behavior	\\
		\hline
			Attack								& Ноги и руки агента				& Атаковать цель с помощью анимации\\
		\hline
			FindPathAstar									&	Нет								& Искать кратчайшего пути с использованием алгоритма A*							\\
		\hline
			GoHome									&	Ноги агента						& Движение  к одной точке  с  использованием  Steering Behavior					\\
		\hline

	\end{tabularx}
\end {table}

\begin{figure}[!ht]
\includegraphics[scale=1]
{1.png}
\caption{\label{fig:pathFind}Диаграмма классов, реализующих алгоритм А-звезды}
\end{figure}


Был спректирован тратегический поиск пути с помощью алгоритма А\*(A-star). Разработка алгоритма поиска пути была описана в разделе \ref{section:Pathfinding}.
Диаграмма классов на рисунке \ref{fig:pathFind} отображает классы, реализующие алгоритм А-звезды.


\section{Результаты тестирования}
 Поведение агетов, управляемых компьютером визуализируется в конкретном систуации:
\begin{itemize}
\item блуждание
\item избегание препятствий
\item прибытие
\item <<думать>>
\item подбор цветка
\end{itemize}

В систуациях <<блуждание>> агент случайно помещает по карте бесценно и когда агент встречает препятствие, он избегает от него.

В систуациях <<избегание препятствий>> агент сама определяет расстояние от его позиции до препятствия. В случае это расстояние больше определенного значения агент вращает на $90^{\circ}$

В систуациях <<прибытие>> агент пододет к цветку. Проверка показывает, что агент при прибытии в определенную цель постепенно замедляется и полностью останавливается, когда достигает этой цель.

Поведение <<думать>> деляется на 2 типа:
\begin{itemize}
\item <<думать>> для решения действия
\item <<думать>> для поиска кратчайшего пути
\end{itemize}

В систуациях <<подбор цветка>> агент одновремено выполняется 2 действия:
\begin{itemize}
\item подбор цветка мечом в руке
\item приход в цветок
\end{itemize}

В ходе проверки тестового примера, агенты в целом демонстрировали
поведение, схожее с игроком-человеком в условиях.

На сцене программы визуализированы координаты агентов, направление движения, направление поиска, текущее действие («думать», поиск, подбор, возврат (<<Go home>>)), а так же пользовательская отладочная информация в виде графических примитивов и текстовых сообщений.

Макет програмы отображен на рисунке \ref{fig:maket}.

\begin{figure}[!ht]
\includegraphics[scale=1]
{maket.png}
\caption{\label{fig:maket}Макет програмы}
\end{figure}

Состояние виртуального мира сохраняется в файл с форматом XML при выходе приложения.

\section{Вывод}
Тестирование модуля показало, что основные требования, предъявляемые модуля выполняются.

Модуль визуализации, реализированный в процессе разработки, выполняет требования визуализации параметров агентов и пользовательской отладочной информации.

Различные поведения агента обновляется быстро при его  изменении тактики. Алгоритмы, реализированные в модуле работают с высокой скоростью.

Программа  является расширяемой.
\conclusion

В данной работе проанализированы существующие системы моделирования поведения ИА, выявлены их недостатки и рассмотрены алгоритмы решения задачи визуализации поведения ИА. Создан симулятор для визуализации поведения ИА. Предложена архитектура системы, в которую модуль визуализации поведения ИА входит. Разработан модуль на основе мультиагентного подхода для визуализации поведения ИА. Визуализируются не только состояние мира, но и параметры каждого агента в определенный момент времени. С помощью мультиагентного подхода разработаны модель агента, модель виртуального мира и механизм взаимодействия между агентами и виртуальным миром. 

Результаты тестирования показали, что модуля позволяет визуализировать параметры агентов в виртуальном мире, частично позволять отладить программу при разработке мультиагентной системы.
Таким образом, все поставленные задачи успешно выполнены.

В сравнении с существующими системами (Mason, Escape, Net Logo, Repast) разработанный модуль устранить их недостатки. В этих системах отладочная информация отображается в формате текстовом и/или графическом формате независимо от положения агента в окружающей среде. Это снижает эффективность процесса отладки, так как разработчик должен фокусировать внимание на двух объектах: агенте и таблице с информацией о нем. В разработанном модуле визуализированы необходимые пользователю параметры и вся отображаемая информация будет привязана к координатам агента. Модуль разработан на языке программирования С++, поэтому он адаптируется с многими платформами (Java, Linux, Mac OSX, и т.д.). 

 Разработанная модуль является гибкой, потому что он может входить в другую систему ИИ для визуализации поведения ИА. Так как входные данные модуля считываются из файла XML, поэтому для применения модуля нужно формировать подходящую архитектуру файла.

В процессе разработки модуля возникали проблемы, которые требуются поправить для применения в реальной мультиагентной системы. Модуль позволяет визуализировать набор фиксированных параметров, а не произвольный набор параметров, задаваемый пользователем. Модуль в настоящее время не используется в системе ИИ, он использует данные из подсистем <<построения сцены>> для визуализации поведения ИА. Параметры агента довольно мало.

В дальнешем можно доработать модуль, исправить все проблемы и использовать модуль для разработки моделей интеллектульных агентов, во время отладки мультиагентной системы и применять его в системе ИИ 

%\bibliography {Bibliography}

% Изменение на прямые ссылки
\begin{thebibliography}{100}
\title{dfdfd}
%references
\bibitem{an-introduction-to-multiagent-systems}~Wooldridge, M. An introduction to mutiagent systems / M.  Wooldridge. England: -- JOHN WILEY \& SONS, LTD, 2002.
\bibitem{AgentsMASVirtualSociety}~Тарасов, В. Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте / В. Б. Тарасов // Новости искусственного интеллекта.  -- 1998. -- Т.2. --  С. 5--63.
\bibitem{tarasov-from-multiagents-to-intelligence}~Тарасов, В. Б. От многоагентных систем к интеллектуальных организациям / В. Б. Тарасов. -- Москва : Едиториал УРСС. -- 2002.
\bibitem{TutorialsAgent-based}~Macal, C. M. Tutorial on agent-based modeling and simulation / C. M. Macal, M. J.  North // In the proceedings of the 2005 Winter Simulation Conference. -- 2005. --  P. 2--15.
\bibitem{Progamming-Game-AI-by-Example}~ Buckland, M. Programming Game AI by Example /  M.Buckland // Americal: -- Wordware Publishing, Inc. -- 2005. -- 495 p.
\bibitem{NetLogoSystem}~Wilensky, U. Официальная страница проекта Netlogo / U. Wilensky. --  The center for Connected Learning (CCL) and Computer-Based Modeling. -- [Электронный ресурс]. -- [2013]. -- Режим доступа: \url{http://ccl.northwestern.edu/netlogo/}
\bibitem{Mason}~Luke, S.  MASON Multiagent Simulation Toolkit / S. Luke. – George Mason University and the GMU Center for Social Complexity [Электронный реcурс]. -- [2013]. -- Режим доступа: \url{ http://cs.gmu.edu/~eclab/projects/mason/}
\bibitem{MasonToolkit}~A New Multi-Agent Simulation Toolkit / L. Sean, C. Claudio, P. Liviu и др. -- [Электронный реcурс]. -- [2013]. -- Режим доступа: \url{http://www.raai.org/resurs/papers/kii-2010/doklad/dobrynin.pdf}
\bibitem{Ascape}~Parker, M. Система моделирования <<Ascape>> / M. Parker, M. Inchiosa, Oliver. -- [Электронный ресурс]. -- [2013]. -- Режим доступа:\url{http://ascape.sourceforge.net/index.html%23Contact}
\bibitem{Repast}~Севера, М. Система моделирования <<Repast>> / М. Севера // Argonne National Laboratory. -- [Электронный ресурс]. -- [ 2013]. -- Режим доступа: \url{http://repast.sourceforge.net}
\bibitem{animationford}~Adams, J. Advanded Animation With DirectX / J. Adams // The Premier Press Game Development Siries. --  Boston : MA 02210. -- 2003.
\bibitem{Half-Life-Game}~Laidlaw, M. Half-Life / M. Laidlaw. Valve Software . -- [Электронный ресурс]. -- [2013]. -- Режим доступа: \url{http://planethalflife.gamespy.com/}
\bibitem{DirectXGraphics}~Eisler, S. DirectX, Microsoft / S. Eisler, E. John. Microsoft . -- [Электронный ресурс]. -- [2013]. -- Режим доступа: \url{http://windows.microsoft.com/en-us/windows7/products/features/directx-11}
\bibitem{openGLGraphics}~Silicon Graphics OpenGL / Silicon Graphics Inc. -- [Электронный ресурс]. -- [2013]. -- Режим доступа: \url{http://www.opengl.org/}
\bibitem{OrgeEngine}~Streeting, S. Orge - Open Source 3D Graphics Engine / S. Streeting. Ogre3D Team. -- [Электронный ресурс]. -- [2013]. – Режим доступа: \url{http://www.ogre3d.org/}
\bibitem{OpenGlStaldart}~OpenGL – Программирование с использованием OpenGL. -- [Электронный ресурс]. -- [2013]. -- Режим доступа: \url{http://www.opengl.org.ru/}
\bibitem{GDIPlus}~Брусенцев, В. GDI+ : графика нового поколения. Работа с растрами и графическими файлами / В. Брусенцев. The RSDN Group. --  [Электронный ресурс]. -- [2013]. -- Режим доступа: \url{http://www.rsdn.ru/article/gdi/gdiplus2mag.xml}
\bibitem{IrrlichtEngine}~Gebhardt, N. Irrlicht Engine - A free open source 3D engine / N. Gebhardt. --  [Электронный ресурс]. -- [2013]. -- Режим доступа:  \url{http://irrlicht.sourceforge.net/}
\bibitem{threeDSimulation}~3D Visualization and Animation of Crowd Simulation Using a Game Engine, School of Computer Engineering Nanyang Technological University / K. Sornum, Y. Liang, W. Cai, M. Yoke //  Nanyang Technological University. -- [Электронный ресурс]. -- [2013]. -- Режим доступа:  \url{http://ebooks6.com/3D-Visualization-and-Animation-of-Crowd-Simulation-Using-a-Game-download-w10936.pdf}
\bibitem{SteeringBehavior}~Reynolds, C. W. Steering behavior for autonomuous characters / C. W. Reynolds. -- Foster City, California, 1999. -- [Электронный ресурс]. -- [2013]. -- Режим доступа: \url{http://www.red3d.com/cwr/steer/gdc99/}
\bibitem{a-star-for-AI}~A* PathFinder In Visual Basic with the A star algorithm. Foxes Team. -- [2005] . -- Режим доступа: \url{http://digilander.libero.it/foxes/Plot/Pathfinder_%20Astar.pdf}
\bibitem{chaperIrrlichtFile}~Irrlicht --- Learning the Basics. [Электронный ресурс]. -- [2005] . -- Режим доступа: \url{http://www.irrlicht3d.org/wiki/index.php?n=Main.IrrlichtManualChapter2}
\end{thebibliography}
\appendix 

\chapter{Техническое задание}
\section {Назначение системы}
\section {Требования}
\subsection {Функциональные требования}
\subsection {Нефункциональные требования}

\chapter{Руководство пользователя}
%\section{}
\chapter{Руководство системного администратора}
%\section{}
\chapter{Раздаточные материалы}
\end {document}